1. Technical Field
The present invention relates to an improved data processing system, and in particular to a method and system for efficiently locating requested data in a cache memory system. Still more particularly, the present invention relates to a method and system for simultaneously utilizing multiple hash functions to locate requested data in a cache memory system.
2. Description of the Related Art
A cache memory is a small, fast, redundant memory used to store the most frequently accessed parts of the main memory. Cache memory provides a buffering capability by which a relatively slow and large main memory can interface to a CPU at the processor cycle time in order to optimize performance. Such system performance may be measured by the ratio of memory access time to processor cycle time. Since cache memory exploits the principle of "locality of reference," and because cache memories operate at close to processor speeds, the use of cache memory may improve overall system performance by lowering the ratio of memory access time to processor cycle time. The principle of locality of reference is based upon the observation that some memory locations are referenced much more frequently than others. By copying into cache memory a copy of data located at a location in main memory which is frequently accessed, system performance may be increased because the likelihood that the CPU must wait for access to data in main memory has decreased.
Cache memory is "associative," or "content-addressable," which means that the address of a memory location is stored, along with the content of that memory location. Rather than reading data directly from a cache memory location, the cache memory is given an address and responds by providing data which may or may not be the data that was requested. The cache then indicates that the correct data is being provided by indicating a "hit." Otherwise the cache indicates a "miss." If the cache indicates a miss, the requested data must then be recalled from main memory or from virtual memory (i.e., a hard disk drive). The performance of a cache memory system may described by a "hit ratio," which is the number of times requested data is found in cache memory compared to the number of times the CPU requests data. The hit ratio is strongly influenced by the program being executed, but is largely independent of the ratio of cache size to memory size.
Because cache memory may only store a copy of a portion of main memory, a strategy for cache management is necessary. Cache management strategies exploit the principle of locality. Spatial locality is exploited in the choice of what data is copied into cache memory. Temporal locality is exploited in the choice of what data is deleted from cache memory. When a cache miss occurs, data processing system hardware copies into cache memory, a large, contiguous block of data that includes the data requested. Such a fixed-size region of memory, known as a cache "line" or "block," may be as small as a single word, or as large as several hundred bytes.
Cache memory often comprises two conventional memories, one known as the data memory, and one as the tag memory. The address of each cache line contained in the data memory is stored in the tag memory, as well as other information (e.g., "state" information). Each line contained in the data memory is allocated a corresponding word in the tag memory to indicate the full address of the cache line.
The requirement that the cache memory be associative complicates the design. Addressing data in memory by the content of the data is inherently more complicated than addressing the data by its address. In addressing data in cache memory, all the tags must be compared concurrently to achieve low latency. In one cache implementation, a mapping of main memory locations to cache memory locations makes the design simpler. This means that the location of data in cache is computed as a function of the main memory address for that data. Such a function for computing a location in cache may be referred to as a "hash function." Typically, a number of the low-order bits of the memory address may be selected by such a hash function.
In such "direct-mapped" caches, each memory location is mapped to a single location in the cache. This may make many aspects of the design simple, since there is no choice as to where the memory line may reside in cache, and no choice as to which line in cache will be deleted when new data is stored. However, the direct mapping may result in poor cache utilization when two memory locations are alternately accessed and must share a single area in cache. This means that multiple memory references may conflict for the same cache entry even when other cache entries are available.
Another method of implementing a cache memory is called a "set-associative cache." Set-associative caches alleviate the problem caused when two memory locations are alternately accessed and must share a single cache cell in a direct-mapped cache. An M-way set-associative cache maps each main memory location into one of M locations in the cache. This permits the cache to be constructed from M number of direct-mapped caches. However, in recalling data from cache, M caches must be searched with each memory access and the appropriate data selected and multiplexed if a match occurs. Upon the occurrence of a miss, a choice must be made regarding which of the M possible lines is to be deleted as new data is copied into the cache. The additional complexity of set-associative caches usually limits the degree (i.e., the number M) of the design. Typically, when M equals 4 or less, set-associative cache memories are still competitive, although a cycle time slower, with direct-mapped caches.
The search for data in a set associative cache location proceeds by computing the memory index as a function of the main memory address. This address is applied to all M memory arrays, and a tag comparison is performed to determine if the requested data is present in cache.
More recently, a class of direct-mapped caches known as "hash-rehash" has been developed. Hash-rehash caches are regular direct-mapped caches that select cache entries for a given memory address by using two hash functions. A first hash function is used to calculate a primary cache address for the requested data. If such a first cache address does not contain the requested data, a second hash function may then be used to calculate an alternative cache location for the requested data. Thus, requested data may be located in two different locations in cache memory as determined by the first and second hash functions.
Cache searches in a hash-rehash cache may take one or two cycles. In the case where a first hash function locates requested data in cache, requested data may be located in one cycle. If a miss occurs utilizing the first hash function, the second hash function may be utilized to locate the requested data in the cache in a second location. If the second location contains the requested data, the cache search has utilized two cycles. hash-rehash caches have been shown to match the hit ratio of a four-way set-associative cache with the same cache memory size. Access times are similar, even though hash-rehash caches may require two cycles per access. This is because misses are relatively rare events.
One problem with the prior art is that the first location in the cache, which is the result of a first hash function, is examined first, before a second hash function calculates an alternative cache location for the requested data. If the requested data is not located at the address produced by the first hash function, the cache address produced by the second hash function is then examined to determine if the requested data is present. As discussed above, the process of searching for requested data in a hash-rehash cache may require two cycles per memory request. Therefore, the problem remaining in the prior art is to provide a hash-rehash cache that allows access to tag memory for two or more hash functions during the same cycle time. If the examination of tag data resulting from tag memory access by two or more hash functions is permitted in the same cycle time, both the performance characteristics of direct-mapped caches and the higher bit ratio of set-associative caches may be obtained.